package com.study.data.structure.binarytree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树
 *
 * @author YangGuGu
 */
public class BinaryTree<K extends Comparable<K>, V> {

  private Node<K, V> root;
  private int size;

  public void put(K key, V value) {
    if (key == null) {
      return;
    }
    root = put(root, key, value);
  }

  /**
   * 给指定树x上，添加键一个键值对，并返回添加后的新树
   *
   * @param node
   *     节点
   * @param key
   *     关键字
   * @param value
   *     节点值
   * @return 新树根节点
   */
  private Node<K, V> put(Node<K, V> node, K key, V value) {
    // 如果 node 为空，则创建 root 节点
    if (node == null) {
      size++;
      return new Node<>(key, value);
    }
    int compareResult = key.compareTo(node.getKey());
    if (compareResult > 0) {
      // 新结点的key大于当前结点的key，继续找当前结点的右子结点
      node.setRight(put(node.getRight(), key, value));
    } else if (compareResult < 0) {
      //新结点的key小于当前结点的key，继续找当前结点的左子结点
      node.setLeft(put(node.getLeft(), key, value));
    } else {
      //新结点的key等于当前结点的key，把当前结点的value进行替换
      node.setValue(value);
    }
    return node;
  }

  public Node<K, V> get(K key) {
    if (key == null) {
      return null;
    }
    if (isEmpty()) {
      return null;
    }
    return get(root, key);
  }

  private Node<K, V> get(Node<K, V> node, K key) {
    if (node == null) {
      return null;
    }
    int compareResult = key.compareTo(node.getKey());
    if (compareResult > 0) {
      //如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
      return get(node.getRight(), key);
    } else if (compareResult < 0) {
      //如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
      return get(node.getLeft(), key);
    } else {
      //如果要查询的key等于当前结点的key，则树中返回当前结点。
      return node;
    }
  }

  public void delete(K key) {
    if (key == null) {
      return;
    }
    if (isEmpty()) {
      return;
    }
    root = delete(root, key);
  }

  /**
   * 删除指定树x上的键为key的键值对，并返回删除后的新树
   *
   * @param node
   *     节点
   * @param key
   *     关键字
   * @return 删除后的新树根节点
   */
  private Node<K, V> delete(Node<K, V> node, K key) {
    int compareResult = key.compareTo(node.getKey());
    if (compareResult > 0) {
      node.setRight(delete(node.getRight(), key));
    } else if (compareResult < 0) {
      node.setLeft(delete(node.getLeft(), key));
    } else {

    }
    return node;
  }

  public Node<K, V> min() {
    return min(root);
  }

  private Node<K, V> min(Node<K, V> node) {
    if (node == null) {
      return null;
    }
    if (node.getLeft() == null) {
      return node;
    }
    return min(node.getLeft());
  }

  public Node<K, V> max() {
    return max(root);
  }

  private Node<K, V> max(Node<K, V> node) {
    if (node == null) {
      return null;
    }
    if (node.getRight() == null) {
      return node;
    }
    return max(node.getRight());
  }

  /**
   * 前序遍历
   */
  public List<Node<K, V>> preErgodic() {
    List<Node<K, V>> result = new ArrayList<>();
    preErgodic(root, result);
    return result;
  }

  private void preErgodic(Node<K, V> node, List<Node<K, V>> nodes) {
    if (node == null) {
      return;
    }
    nodes.add(node);
    preErgodic(node.getLeft(), nodes);
    preErgodic(node.getRight(), nodes);
  }

  /**
   * 中序遍历
   */
  public List<Node<K, V>> midErgodic() {
    List<Node<K, V>> result = new ArrayList<>();
    midErgodic(root, result);
    return result;
  }

  private void midErgodic(Node<K, V> node, List<Node<K, V>> nodes) {
    if (node == null) {
      return;
    }
    preErgodic(node.getLeft(), nodes);
    nodes.add(node);
    preErgodic(node.getRight(), nodes);
  }

  /**
   * 后序遍历
   */
  public List<Node<K, V>> afterErgodic() {
    List<Node<K, V>> result = new ArrayList<>();
    afterErgodic(root, result);
    return result;
  }

  private void afterErgodic(Node<K, V> node, List<Node<K, V>> nodes) {
    if (node == null) {
      return;
    }
    preErgodic(node.getLeft(), nodes);
    preErgodic(node.getRight(), nodes);
    nodes.add(node);
  }

  /**
   * 层序遍历
   */
  public List<Node<K, V>> layerErgodic() {
    if (root == null) {
      return Collections.emptyList();
    }
    List<Node<K, V>> result = new ArrayList<>();

    Queue<Node<K, V>> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
      Node<K, V> node = queue.poll();
      if (node == null) {
        break;
      }
      result.add(node);

      if (node.getLeft() != null) {
        queue.add(node.getLeft());
      }

      if (node.getRight() != null) {
        queue.add(node.getRight());
      }
    }
    return result;
  }

  public boolean isEmpty() {
    return getSize() == 0;
  }

  public int getSize() {
    return size;
  }
}
